package com.lh.nk;

/**
 * @author: linghao
 * @since: 2023/2/4
 *
 * 描述: 要求时间复杂度 O(n)
 * 输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值
 *
 * [1,-2,3,10,-4,7,2,-5] 经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18
 *
 */
public class 连续子数组的最大和NC19 {

    //暴力破解  O(N2)
    /*public int FindGreatestSumOfSubArray(int[] array) {
        int max = 0;
        int sum = 0;
        for(int i=0;i<array.length;i++){
            sum = 0;
            for(int j=i;j<array.length;j++){
                sum += array[j];
                max = Math.max(max,sum);
            }
        }
        return max;
    }*/


    //动态规划，动态规划转移转移方程 dp[i] = Math.max(dp[i-1]+array[i],array[i]); 因为一个数字也是子串
    public int FindGreatestSumOfSubArray1(int[] array){
        int[] dp = new int[array.length];
        dp[0] = array[0];
        int max = array[0];
        for(int i=1;i<array.length;i++){
            dp[i] = Math.max(dp[i-1]+array[i],array[i]);
            max = Math.max(dp[i],max);
        }
        return max;
    }

    //动态规划 优化版 空间复杂度变为 O[1]
    public int FindGreatestSumOfSubArray2(int[] array){
        int max = array[0];
        int sum = array[0];
        for(int i=1;i<array.length;i++){
            sum = Math.max(sum+array[i],array[i]);
            max = Math.max(max,sum);
        }
        return max;
    }
}
